Entropy or arithmetic coding is a form of data coding that can be used to compactly represent data, and may be used in one phase of an image compression algorithm. For example, a proposed image compression standard referred to as JPEG 2000 employs entropy coding as a final data coding process in an algorithm for still image compression. The JPEG 2000 algorithm is described, for example, in the Joint Photographic Experts Group JPEG 2000 Image Coding System document (ITU-T Rec. T.800 (1999 CDV1.0)/ISO/IEC CD15444-1:1999(V1.0, 9 Dec. 1999)), the disclosure of which is incorporated herein by reference. The JPEG 2000 image compression system is used as a basis upon which to describe the operation of the present invention, and is thus introduced briefly hereinbelow.
Referring to FIG. 1, raw image data 10 to be compressed is first decomposed into components (step 12). For example, an image represented in an RGB color format may be decomposed into three separate color components. The image components are then each divided into tiles (step 14). The tiles are rectangular arrays applied in the same manner to each of the image components. The tile-components are further decomposed into different decomposition levels using a wavelet transform (step 16). The wavelet transform decomposition levels contain a number of sub-bands populated with coefficients that describe horizontal and vertical spatial frequency characteristics of the original tile-component planes (step 18). The coefficients provide local frequency information, and each wavelet decomposition level is related to the next decomposition level by spatial powers of two. In other words, each successive decomposition level of the sub-bands has approximately half of the horizontal and half of the vertical resolution as the previous level.
Even though there may be as many wavelet transform coefficients as original image samples, the information content following the wavelet transform tends to be concentrated into a relatively few coefficients. Using quantization, the information content can be further concentrated in the wavelet transform coefficients. Following quantization, the individual sub-bands of a tile component are divided into rectangular arrays of coefficients, referred to as code-blocks (step 20). The individual bit-planes of the coefficients in a code block are then entropy coded in three coding passes (step 22). Each of the coding passes collects contextual information about the bit-plane data and the arithmetic coder uses the contextual information and its internal state to generate coded data 24 that can then be formed into a compressed bit-stream (step 26).